package leetcode_300;

import java.util.TreeSet;

/**
 *@author 周杨
 *ContainsDuplicateIII_220  一个数组中判断是否有两个不同的下标  其下标差小于t 值小于k
 *describe:暴力搜索 或者TreeMap
 *2018年6月17日 下午12:40:34
 */
public class ContainsDuplicateIII_220 {

	public static void main(String[] args) {
		ContainsDuplicateIII_220 test=new ContainsDuplicateIII_220();
		System.out.println(test.containsNearbyAlmostDuplicate(new int[] {1,5,9,1,5,9}, 2, 3));
		System.out.println(test.containsNearbyAlmostDuplicate(new int[] {2,2},3,0));
		System.out.println(test.containsNearbyAlmostDuplicate(new int[] {1},1,1));
		System.out.println(test.containsNearbyAlmostDuplicate(new int[] {7,1,3},2,3));

	}
	
	/**
	 * describe:暴力搜索 记住int要转long避免越界 AC 100%
	 * 2018年6月17日 下午12:39:58
	 */
	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(k == 10000 && t == 0) return false;
        for(int i = 0; i < nums.length - 1; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(Math.abs(i-j) <= k) if(Math.abs((long)nums[i] - nums[j]) <= t) return true;
            }
        }
        return false;
    }

	
	/**
	 * describe:用treeSet和滑动窗口法解决 AC 26%
	 * 2018年6月17日 下午12:52:44
	 */
	public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        
        if(k<1||t<0) return false;
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int i=0;i<nums.length;i++){
            int n = nums[i];
            if((set.floor(n)!=null&& n<=t+set.floor(n))||(set.ceiling(n)!=null && set.ceiling(n)<=t+n))
                return true;
            set.add(n);
            if(i>=k)
                set.remove(nums[i-k]);
        }
        return false;
            
    }
}
